#include <stdio.h>
#include <math.h>
#include <stdlib.h>

/*
	用非递归方式实现归并排序。
*/

void MergeSortPart(int array[], int left, int mid, int right)
{
	int merged[right - left + 1];
	int i = left, j = mid + 1;
	int p = 0;
	while (i <= mid && j <= right)
	{
		if (array[i] <= array[j])
		{
			merged[p++] = array[i++];
		}
		else
		{
			merged[p++] = array[j++];
		}
	}
	while (i <= mid)
	{
		merged[p++] = array[i++];
	}
	while (j <= right)
	{
		merged[p++] = array[j++];
	}
	i = left;
	p = 0;
	while (i <= right)
	{
		array[i++] = merged[p++];
	}
}

void MergeSort(int array[], int n)
{
	int size, left, right, mid;
	for (size = 1; size < n; size *= 2)
	{
		for (left = 0; left < n; left += 2 * size)
		{
			right = left + 2 * size - 1;
			mid = (left + right) / 2;
			right = right > (n - 1) ? (n - 1) : right;
			if (mid < right)
			{
				MergeSortPart(array, left, mid, right);
			}
		}
	}
}

int main()
{
	int array[1000];
	int i;
	for (i = 0; i < 1000; i++)
	{
		array[i] = rand() % 10000;
	}
	MergeSort(array, 1000);
	int tag = 0;
	for (int i = 0; i < 999; i++)
	{
		if (array[i] > array[i + 1])
		{
			tag = -1;
			break;
		}
	}
	printf("tag=%d\n", tag);
	return 0;
}
